<!DOCTYPE html>





<html class="theme-next gemini use-motion" lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="generator" content="Hexo 3.9.0">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=7.3.0">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=7.3.0">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=7.3.0">
  <link rel="mask-icon" href="/images/logo.svg?v=7.3.0" color="#222">
  <meta name="google-site-verification" content="uSLhm-2JUAoM7eOTok7L19IyTJqp7dgwYpDu8dthN5Y" />

<link rel="stylesheet" href="/css/main.css?v=7.3.0">


<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css?v=4.7.0">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/gh/theme-next/theme-next-needmoreshare2@1/needsharebutton.min.css">
  <link rel="stylesheet" href="/lib/pace/pace-theme-center-atom.min.css?v=1.0.2">
  <script src="/lib/pace/pace.min.js?v=1.0.2"></script>


<script id="hexo-configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '7.3.0',
    exturl: false,
    sidebar: {"position":"left","display":"post","offset":12,"onmobile":true},
    back2top: {"enable":true,"sidebar":true,"scrollpercent":true},
    save_scroll: false,
    copycode: {"enable":true,"show_result":true,"style":"mac"},
    fancybox: false,
    mediumzoom: false,
    lazyload: false,
    pangu: false,
    algolia: {
      appID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    },
    localsearch: {"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},
    path: '',
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    translation: {
      copy_button: '复制',
      copy_success: '复制成功',
      copy_failure: '复制失败'
    }
  };
</script>

  <meta name="description" content="前言本来什么都不会的… 但是呢, 为了能顺利进入MSC in XDU去打ACM, 我就只能硬着头皮上啦…">
<meta name="keywords" content="编程,算法,ACM-ICPC学习">
<meta property="og:type" content="article">
<meta property="og:title" content="网络流学习1--最大流问题">
<meta property="og:url" content="https://www.wootec.top/2019/09/20/网络流学习/index.html">
<meta property="og:site_name" content="Reverier 个人博客">
<meta property="og:description" content="前言本来什么都不会的… 但是呢, 为了能顺利进入MSC in XDU去打ACM, 我就只能硬着头皮上啦…">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="https://i.loli.net/2019/09/20/HORsoei4UpdNnmF.jpg">
<meta property="og:updated_time" content="2019-09-22T16:19:01.303Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="网络流学习1--最大流问题">
<meta name="twitter:description" content="前言本来什么都不会的… 但是呢, 为了能顺利进入MSC in XDU去打ACM, 我就只能硬着头皮上啦…">
<meta name="twitter:image" content="https://i.loli.net/2019/09/20/HORsoei4UpdNnmF.jpg">
  <link rel="alternate" href="/atom.xml" title="Reverier 个人博客" type="application/atom+xml">
  <link rel="canonical" href="https://www.wootec.top/2019/09/20/网络流学习/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome: false,
    isPost: true,
    isPage: false,
    isArchive: false
  };
</script>

  <title>网络流学习1--最大流问题 | Reverier 个人博客</title>
  








  <noscript>
  <style>
  .use-motion .motion-element,
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-title { opacity: initial; }

  .use-motion .logo,
  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  <div class="container sidebar-position-left">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta">

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Reverier 个人博客</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
        <p class="site-subtitle">Hope, Marvel, Youth.</p>
      
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>


<nav class="site-nav">
  
  <ul id="menu" class="menu">
      
      
      
        
        <li class="menu-item menu-item-home">
      
    
      
    

    <a href="/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i> <br>首页</a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-about">
      
    
      
    

    <a href="/about/" rel="section"><i class="menu-item-icon fa fa-fw fa-user"></i> <br>关于</a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-tags">
      
    
      
    

    <a href="/tags/" rel="section"><i class="menu-item-icon fa fa-fw fa-tags"></i> <br>标签<span class="badge">15</span></a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-categories">
      
    
      
    

    <a href="/categories/" rel="section"><i class="menu-item-icon fa fa-fw fa-th"></i> <br>分类<span class="badge">11</span></a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-archives">
      
    
      
    

    <a href="/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i> <br>归档<span class="badge">16</span></a>

  </li>
  </ul>

</nav>
</div>
    </header>

    

  <a href="https://github.com/Reverier-Xu" class="github-corner" title="My tour on GitHub" aria-label="My tour on GitHub" rel="noopener" target="_blank"><svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></a>


    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
            

          <div id="content" class="content page-post-detail">
            

  <div id="posts" class="posts-expand">
    

  <article class="post" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://www.wootec.top/2019/09/20/网络流学习/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="Reverier Xu">
      <meta itemprop="description" content="Hope, Marvel, Youth.">
      <meta itemprop="image" content="/images/Reverier.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Reverier 个人博客">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">网络流学习1--最大流问题

          
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              
                
              

              <time title="创建时间：2019-09-20 16:40:27" itemprop="dateCreated datePublished" datetime="2019-09-20T16:40:27+08:00">2019-09-20</time>
            </span>
          
            

            
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2019-09-23 00:19:01" itemprop="dateModified" datetime="2019-09-23T00:19:01+08:00">2019-09-23</time>
              </span>
            
          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/算法/" itemprop="url" rel="index"><span itemprop="name">算法</span></a></span>

                
                
              
            </span>
          

          
            <span class="post-meta-item" title="阅读次数">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">阅读次数：</span>
              <span class="busuanzi-value" id="busuanzi_value_page_pv"></span>
            </span>
          

                    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h1 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h1><p>本来什么都不会的… 但是呢, 为了能顺利进入MSC in XDU去打ACM, 我就只能硬着头皮上啦…</p>
<a id="more"></a>

<h1 id="网络流是什么"><a href="#网络流是什么" class="headerlink" title="网络流是什么"></a>网络流是什么</h1><h2 id="通俗的解释"><a href="#通俗的解释" class="headerlink" title="通俗的解释"></a>通俗的解释</h2><p>什么是网络流呢???</p>
<p>某升专门去Google学术搜索了一下, 然后发现我什么也看不懂… 无奈翻出紫书开始研究, 用一个通俗的方式讲, 就是一张地图,许多城市, 不同城市间有道路, 但是为了防止事故, 都是单行道. 这些道路各有宽窄, 宽的路自然就运的东西多啦… 各个道路组成了一张道路交通网, 我们可以将其抽象化为<code>网络</code>这个词. 而网络流里面的<code>流</code>, 指的就是车辆运输的东西啦 ( 溜 ). 一条路所能承载的最大运输量, 称之为<code>流量</code>. 这大概就解释了一个十分清晰的网络流模型了…</p>
<h1 id="最大流问题"><a href="#最大流问题" class="headerlink" title="最大流问题"></a>最大流问题</h1><h2 id="通俗的解释-1"><a href="#通俗的解释-1" class="headerlink" title="通俗的解释"></a>通俗的解释</h2><p>现在, 假设某升有天发达了在A市开了个仓库, 现在某升希望从A市向很远的B市运输东西, 但是呢, 每跑一次都要花费大量的人力物力, 所以需要找到一条路, 使得从A市到B市的一次运输能尽可能多的带东西过去.. 现在需要找到一条道路, 并求出理论上能运输的物品的最大数量… </p>
<p>第一次看这种问题感觉似乎不是很难? 广度优先搜索应该可以搞定吧 ( 汗 )… </p>
<h2 id="概念"><a href="#概念" class="headerlink" title="概念"></a>概念</h2><p>我们可以画一张简单的图:</p>
<p><img src="https://i.loli.net/2019/09/20/HORsoei4UpdNnmF.jpg" alt="最大流1.jpg"></p>
<p>这张粗陋的图简单的写了一下刚刚某升运货的情况… 从A市到B市间隔了V1~V4四座城市, 某升可以在这里稍作停留. 问走哪条路才是最佳的选择呢?  在这张图里, 对于一条道路(u, v), 我们把它的运输上限称为容量(Capacity), 记为<code>c(u, v)</code>, 把实际能运送的物品叫做流量(Flow), 记为<code>f(u, v)</code>. 我们还可以发现A只出不进, B只进不出, 而其他的节点都会有进出. 在问题之中, 应当明确, 当运输任务完成时, A的输出量就是B的输入量 ( 否则某升就亏大了..</p>
<h1 id="增广路算法"><a href="#增广路算法" class="headerlink" title="增广路算法"></a>增广路算法</h1><h2 id="介绍"><a href="#介绍" class="headerlink" title="介绍"></a>介绍</h2><p>既然了解了这个问题, 就得想办法去解决它… 怎么解决呢? 这里有一种叫做增广路算法的东西.. 具体做法, 就是先建一个空图, 然后从零流量开始, 不断地增加流量, 保证每次增加之后都满足对于每条路: <code>f(u, v) == -f(v, u)</code>, 每条路上的流量不超过路容量, 以及A市输出和B市输入是一致的. 这三个特性分别称为 <code>斜对称性</code>, <code>容量限制</code>, <code>流量平衡</code>.</p>
<p>我们把每条边上的容量和流量之差称之为<code>残量</code>, 就是残余容量的意思, 这样的话残量网络就会多出几条返回的道路. </p>
<p>现在我们可以发现一个惊人的事实: 残量网络中任何一条从A市到B市的道路都对应原来网络中一条增广路—意思就是只要求出所有可行道路中的最小残量<code>d</code> , 把所有边上的流量增加<code>d</code>即可. 这个过程就叫增广!</p>
<p>只要残量网络中存在增广路, 那么流量就有继续增大的方法; 当然, 如果不存在增广路了, 那么就说明我们的算法达成目的了!</p>
<h2 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h2><p>好了, 了解了这么多, 我怎么写这个代码呢???</p>
<p>最先想到的毫无疑问是<code>DFS</code>啦… 找路径用<code>DFS</code>还不快? 但是…想不出来<code>DFS</code>写出来的代码应该怎么去增流和维护… 这样一来, 就算实现了, 似乎也很容易爆时间… 那我们换种方法.. 通过紫书上说的, 有种基于<code>BFS</code>的<code>Edmonds-Karp</code>算法, 对付数据不刁钻的题目很好用.. 等我把代码抄一遍…</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> INF = <span class="number">0x7f7f7f7f</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> dis[<span class="number">2001</span>],   <span class="comment">// 流量</span></span><br><span class="line">    head[<span class="number">2001</span>],</span><br><span class="line">    nxt[<span class="number">600001</span>], <span class="comment">// 邻接表存储</span></span><br><span class="line">    before[<span class="number">600001</span>],</span><br><span class="line">    value[<span class="number">600001</span>], <span class="comment">// 路的容量</span></span><br><span class="line">    S, T,        <span class="comment">// 源和汇</span></span><br><span class="line">    num[<span class="number">501</span>],    <span class="comment">// 存储输入数组</span></span><br><span class="line">    n, k = <span class="number">1</span>,    <span class="comment">// n是用来存储数组长度的</span></span><br><span class="line">    flow[<span class="number">501</span>];      <span class="comment">// f用来存储流</span></span><br><span class="line"><span class="keyword">int</span> q[<span class="number">2001</span>], h, t, p[<span class="number">2001</span>], maxlen;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> from, <span class="keyword">int</span> to, <span class="keyword">int</span> val)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    k++;     <span class="comment">// 递增边的数量</span></span><br><span class="line">    nxt[k] = head[from]; <span class="comment">// 然后设置</span></span><br><span class="line">    head[from] = k;</span><br><span class="line">    before[k] = to;</span><br><span class="line">    value[k] = val;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">link</span><span class="params">(<span class="keyword">int</span> from, <span class="keyword">int</span> to, <span class="keyword">int</span> value)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    push(from, to, value); <span class="comment">// 正向建路</span></span><br><span class="line">    push(to, from, <span class="number">0</span>); <span class="comment">// 反向建路, 这样以后回退起来计算着很方便</span></span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">bfs</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">memset</span>(dis, <span class="number">0</span>, <span class="keyword">sizeof</span> dis); <span class="comment">// 首先初始化distance</span></span><br><span class="line">    dis[S] = <span class="number">1</span>;</span><br><span class="line">    h = t = <span class="number">0</span>;</span><br><span class="line">    q[++t] = S;</span><br><span class="line">    <span class="keyword">while</span> (h &lt; t)</span><br><span class="line">    &#123;</span><br><span class="line">        ++h;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = head[q[h]]; i; i = nxt[i])</span><br><span class="line">            <span class="keyword">if</span> (value[i] &amp;&amp; !dis[before[i]])</span><br><span class="line">            &#123;</span><br><span class="line">                dis[before[i]] = dis[q[h]] + <span class="number">1</span>;</span><br><span class="line">                q[++t] = before[i];</span><br><span class="line">                <span class="keyword">if</span> (before[i] == T)</span><br><span class="line">                    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> flow)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (x == T || !flow)</span><br><span class="line">        <span class="keyword">return</span> flow;</span><br><span class="line">    <span class="keyword">int</span> used = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = p[x]; i; i = nxt[i])</span><br><span class="line">        <span class="keyword">if</span> (value[i] &amp;&amp; dis[before[i]] == dis[x] + <span class="number">1</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">int</span> w = dfs(before[i], min(flow - used, value[i]));</span><br><span class="line">            value[i] -= w;</span><br><span class="line">            value[i ^ <span class="number">1</span>] += w;</span><br><span class="line">            used += w;</span><br><span class="line">            <span class="keyword">if</span> (w)</span><br><span class="line">                p[x] = i;</span><br><span class="line">            <span class="keyword">if</span> (used == flow)</span><br><span class="line">                <span class="keyword">return</span> used;</span><br><span class="line">        &#125;</span><br><span class="line">    <span class="keyword">if</span> (!used)</span><br><span class="line">        dis[x] = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">return</span> used;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">cin</span> &gt;&gt; n;</span><br><span class="line">    S = <span class="number">0</span>, T = n * <span class="number">2</span> + <span class="number">1</span>; <span class="comment">// 把汇设置成了两倍加一</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">        <span class="built_in">cin</span> &gt;&gt; num[i];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; i; j++)</span><br><span class="line">            <span class="keyword">if</span> (num[j] &lt;= num[i] &amp;&amp; flow[j] &gt; flow[i])</span><br><span class="line">                flow[i] = flow[j];</span><br><span class="line">        flow[i]++;</span><br><span class="line">        maxlen = max(maxlen, flow[i]);</span><br><span class="line">    &#125; <span class="comment">// 建流</span></span><br><span class="line">    <span class="comment">//接下来使用上述介绍的方法建图</span></span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; maxlen &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">        link(i, i + n, <span class="number">1</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">        <span class="keyword">if</span> (flow[i] == <span class="number">1</span>)</span><br><span class="line">            link(S, i, <span class="number">1</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">        <span class="keyword">if</span> (flow[i] == maxlen)</span><br><span class="line">            link(i + n, T, <span class="number">1</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; i; j++)</span><br><span class="line">            <span class="keyword">if</span> (num[j] &lt;= num[i] &amp;&amp; flow[j] == flow[i] - <span class="number">1</span>)</span><br><span class="line">                link(j + n, i, <span class="number">1</span>); <span class="comment">// 建图完毕</span></span><br><span class="line">    <span class="keyword">int</span> ans = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (bfs())</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">memcpy</span>(p, head, <span class="keyword">sizeof</span>(p));</span><br><span class="line">        ans += dfs(S, INF);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; ans &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    link(<span class="number">1</span>, <span class="number">1</span> + n, INF), link(S, <span class="number">1</span>, INF);</span><br><span class="line">    <span class="keyword">if</span> (flow[n] == maxlen)</span><br><span class="line">        link(n + n, T, INF), link(n, n * <span class="number">2</span>, INF);</span><br><span class="line">    <span class="keyword">while</span> (bfs())</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">memcpy</span>(p, head, <span class="keyword">sizeof</span>(p));</span><br><span class="line">        ans += dfs(S, INF);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; ans &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


      
    </div>

    
    
    
<div>
  
    <div>
    
        <div style="text-align:center;color: #ccc;font-size:14px;">--本文结束-😁-感谢您的阅读!--</div>
    
</div>

  
</div>
      

      

      
        
      
      

      

      <footer class="post-footer">
        
          
            
          
          <div class="post-tags">
            
              <a href="/tags/编程/" rel="tag"><i class="fa fa-tag"></i> 编程</a>
            
              <a href="/tags/算法/" rel="tag"><i class="fa fa-tag"></i> 算法</a>
            
              <a href="/tags/ACM-ICPC学习/" rel="tag"><i class="fa fa-tag"></i> ACM-ICPC学习</a>
            
          </div>
        

        
  <div class="post-widgets">
    <div class="social-share">
      
      
        <div id="needsharebutton-postbottom">
          <span class="btn">
            <i class="fa fa-share-alt" aria-hidden="true"></i>
          </span>
        </div>
      
    </div>
  
  </div>


        
          <div class="post-nav">
            <div class="post-nav-next post-nav-item">
              
                <a href="/2019/09/18/记一次狗屎的HTTP请求头/" rel="next" title="记一次终极狗屎的HTTP请求头">
                  <i class="fa fa-chevron-left"></i> 记一次终极狗屎的HTTP请求头
                </a>
              
            </div>

            <span class="post-nav-divider"></span>

            <div class="post-nav-prev post-nav-item">
              
                <a href="/2019/10/12/生物医学工程报告/" rel="prev" title="生物医学工程报告">
                  生物医学工程报告 <i class="fa fa-chevron-right"></i>
                </a>
              
            </div>
          </div>
        
      </footer>
    
  </div>
  
  
  
  </article>
  </div>


          </div>
          
    
    
  <div class="comments" id="comments">
    <div id="lv-container" data-id="city" data-uid="MTAyMC80NjE1MC8yMjY2MQ=="></div>
  </div>
  
  

        </div>
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-overview">

          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image"
      src="/images/Reverier.png"
      alt="Reverier Xu">
  <p class="site-author-name" itemprop="name">Reverier Xu</p>
  <div class="site-description motion-element" itemprop="description">Hope, Marvel, Youth.</div>
</div>
  <nav class="site-state motion-element">
      <div class="site-state-item site-state-posts">
        
          <a href="/archives/">
        
          <span class="site-state-item-count">16</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
    
      
      
      <div class="site-state-item site-state-categories">
        
          
            <a href="/categories/">
          
        
        
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
        <span class="site-state-item-count">11</span>
        <span class="site-state-item-name">分类</span>
        </a>
      </div>
    
      
      
      <div class="site-state-item site-state-tags">
        
          
            <a href="/tags/">
          
        
        
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
        <span class="site-state-item-count">15</span>
        <span class="site-state-item-name">标签</span>
        </a>
      </div>
    
  </nav>
  <div class="feed-link motion-element">
    <a href="/atom.xml" rel="alternate">
      <i class="fa fa-rss"></i>RSS
    </a>
  </div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
      
      
        
      
      
        <a href="https://github.com/Reverier-Xu" title="GitHub &rarr; https://github.com/Reverier-Xu" rel="noopener" target="_blank">GitHub</a>
      </span>
    
      <span class="links-of-author-item">
      
      
        
      
      
        <a href="https://stackoverflow.com/users/12383772/reverier" title="StackOverflow &rarr; https://stackoverflow.com/users/12383772/reverier" rel="noopener" target="_blank">StackOverflow</a>
      </span>
    
      <span class="links-of-author-item">
      
      
        
      
      
        <a href="mailto:reverier.xu@gmail.com" title="E-Mail &rarr; mailto:reverier.xu@gmail.com" rel="noopener" target="_blank">E-Mail</a>
      </span>
    
      <span class="links-of-author-item">
      
      
        
      
      
        <a href="https://weibo.com/dreamskytech" title="微博 &rarr; https://weibo.com/dreamskytech" rel="noopener" target="_blank">微博</a>
      </span>
    
      <span class="links-of-author-item">
      
      
        
      
      
        <a href="https://www.zhihu.com/people/reverier-78/activities" title="知乎 &rarr; https://www.zhihu.com/people/reverier-78/activities" rel="noopener" target="_blank">知乎</a>
      </span>
    
      <span class="links-of-author-item">
      
      
        
      
      
        <a href="https://user.qzone.qq.com/773389969" title="Qzone &rarr; https://user.qzone.qq.com/773389969" rel="noopener" target="_blank">Qzone</a>
      </span>
    
  </div>
  <div class="cc-license motion-element" itemprop="license">
    
  
    <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" class="cc-opacity" rel="noopener" target="_blank"><img src="/images/cc-by-nc-sa.svg" alt="Creative Commons"></a>
  </div>


  <div class="links-of-blogroll motion-element links-of-blogroll-block">
    <div class="links-of-blogroll-title">
      <i class="fa  fa-fw fa-link"></i>
      友情链接~
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-item">
          <a href="https://www.std-frank.club/" title="https://www.std-frank.club/" rel="noopener" target="_blank">Frank</a>
        </li>
      
        <li class="links-of-blogroll-item">
          <a href="https://eqqie.cn/" title="https://eqqie.cn/" rel="noopener" target="_blank">赤道企鹅</a>
        </li>
      
        <li class="links-of-blogroll-item">
          <a href="https://cor1e.cn/" title="https://cor1e.cn/" rel="noopener" target="_blank">Cor1e</a>
        </li>
      
        <li class="links-of-blogroll-item">
          <a href="https://yunq1ao.com/" title="https://yunq1ao.com/" rel="noopener" target="_blank">yunq1ao</a>
        </li>
      
        <li class="links-of-blogroll-item">
          <a href="https://shal10w.github.io/" title="https://shal10w.github.io/" rel="noopener" target="_blank">shal10w</a>
        </li>
      
        <li class="links-of-blogroll-item">
          <a href="https://blog.csdn.net/arttnba3/" title="https://blog.csdn.net/arttnba3/" rel="noopener" target="_blank">arttnba3</a>
        </li>
      
    </ul>
  </div>


        </div>
      </div>
      <!--noindex-->
        <div class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
            
            
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#前言"><span class="nav-number">1.</span> <span class="nav-text">前言</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#网络流是什么"><span class="nav-number">2.</span> <span class="nav-text">网络流是什么</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#通俗的解释"><span class="nav-number">2.1.</span> <span class="nav-text">通俗的解释</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#最大流问题"><span class="nav-number">3.</span> <span class="nav-text">最大流问题</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#通俗的解释-1"><span class="nav-number">3.1.</span> <span class="nav-text">通俗的解释</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#概念"><span class="nav-number">3.2.</span> <span class="nav-text">概念</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#增广路算法"><span class="nav-number">4.</span> <span class="nav-text">增广路算法</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#介绍"><span class="nav-number">4.1.</span> <span class="nav-text">介绍</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#代码"><span class="nav-number">4.2.</span> <span class="nav-text">代码</span></a></li></ol></li></ol></div>
            

          </div>
        </div>
      <!--/noindex-->
      
        <div class="back-to-top motion-element">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2019 – <span itemprop="copyrightYear">2020</span>
  <span class="with-love" id="animate">
    <i class="fa fa-free-code-camp"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Reverier Xu</span>
</div>
<script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
  

        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item-icon">
      <i class="fa fa-user"></i>
    </span>
    <span class="site-uv" title="总访客量">
      <span class="busuanzi-value" id="busuanzi_value_site_uv"></span>
    </span>
  
    <span class="post-meta-divider">|</span>
  
    <span class="post-meta-item-icon">
      <i class="fa fa-eye"></i>
    </span>
    <span class="site-pv" title="总访问量">
      <span class="busuanzi-value" id="busuanzi_value_site_pv"></span>
    </span>
  
</div>








        
      </div>
    </footer>
      <div class="reading-progress-bar"></div>

    
  
  <div id="needsharebutton-float">
    <span class="btn">
      <i class="fa fa-share-alt" aria-hidden="true"></i>
    </span>
  </div>
<script src="//cdn.jsdelivr.net/gh/theme-next/theme-next-needmoreshare2@1/needsharebutton.min.js"></script>
<script>
    pbOptions = {};
      pbOptions.iconStyle = "default";
    
      pbOptions.boxForm = "horizontal";
    
      pbOptions.position = "bottomCenter";
    
      pbOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
    
    new needShareButton('#needsharebutton-postbottom', pbOptions);
    flOptions = {};
      flOptions.iconStyle = "default";
    
      flOptions.boxForm = "horizontal";
    
      flOptions.position = "middleRight";
    
      flOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
    
    new needShareButton('#needsharebutton-float', flOptions);
</script>


  </div>

  
    
  
  <script color='0,0,255' opacity='0.5' zIndex='-1' count='99' src="/lib/canvas-nest/canvas-nest.min.js"></script>
  <script src="/lib/jquery/index.js?v=3.4.1"></script>
  <script src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  <script src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

<script src="/js/utils.js?v=7.3.0"></script><script src="/js/motion.js?v=7.3.0"></script>

<script src="/js/schemes/pisces.js?v=7.3.0"></script>



<script src="/js/next-boot.js?v=7.3.0"></script>




  
  <script>
    (function(){
      var bp = document.createElement('script');
      var curProtocol = window.location.protocol.split(':')[0];
      bp.src = (curProtocol === 'https') ? 'https://zz.bdstatic.com/linksubmit/push.js' : 'http://push.zhanzhang.baidu.com/push.js';
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(bp, s);
    })();
  </script>




























  

  

  


  
  <script src="/js/scrollspy.js?v=7.3.0"></script><script src="/js/post-details.js?v=7.3.0"></script>


<script>
  window.livereOptions = {
    refer: location.pathname.replace(CONFIG.root, '').replace('index.html', '')
  };
  (function(d, s) {
    var j, e = d.getElementsByTagName(s)[0];
    if (typeof LivereTower === 'function') { return; }
    j = d.createElement(s);
    j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
    j.async = true;
    e.parentNode.insertBefore(j, e);
  })(document, 'script');
</script>

  <link rel="stylesheet" href="/dist/APlayer.min.css">
  <div id="aplayer"></div>
  <script type="text/javascript" src="/dist/APlayer.min.js"></script>
  <script type="text/javascript" src="/dist/music.js"></script>
</body>
</html>
<!-- 页面点击小红心 -->
<script type="text/javascript" src="/js/src/clicklove.js"></script>
